# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        curSum = 0
        maxSum = -1
        for i in array:
            curSum += i
            if curSum > maxSum:
                maxSum = curSum
            if curSum < 0:
                curSum = 0
        return maxSum


class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        sum = 0
        sum_list = []
        for i in array:
            sum += i
            sum_list.append(sum)
            if sum > 0:

                continue
            else:
                sum = 0
        return max(sum_list)
# 动态规划 每一个解都对应上一个值
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        n=len(array)
        dp=[i for i in array]
        for i in range(1,n):
            dp[i]=max(dp[i-1]+array[i],array[i])
        return max(dp)